1. Technical Field
The present invention relates generally to data processing systems, and in particular, to systems and methods for scheduling task execution to provide improved reliability while maintaining acceptable runtime performance.
2. Description of the Related Art
Data processing systems utilize a multitasking approach to handle parallel execution of multiple processes or tasks. Multitasking operations are typically controlled by an operating system executive referred to as the “kernel.” The kernel generally provides an interface between the central processing unit (CPU) and the tasks or processes to be executed. The kernel schedules the execution of the tasks in a manner such that the CPU is shared by all of the concurrently running applications in the system. In this manner, the kernel effectively controls which task has “possession” of the CPU at a given time.
Conventional kernel schedulers determine task possession of the CPU in accordance with a queueing order in which priority and readiness levels are assigned to each task. Typically, the CPU continues execution of a task until it blocks or a system event triggers task rescheduling. The running task is interrupted and “suspended,” and another task, which is selected based on or more factors such as priority, usage penalty, etc., gains possession of the CPU resource and is executed. Task interruption in this manner often occurs many times prior to completion of the task. Upon completion of the higher priority tasks, the CPU is voluntarily surrendered such that the multiple-suspended lower priority tasks are eventually completed.
Tasks in a multitasking environment may be designated as having one of three basic states. An “active” task presently has control of the CPU and is being executed. Only one task is active at any given time on a typical single CPU system. An “inactive” task is neither being executed nor awaiting execution (e.g. a task waiting for an I/O to complete). A “ready” task is waiting for CPU time (i.e., suspended or otherwise waiting to be executed). Upon occurrence of an input/output (I/O) event, an associated task may switch between an “active” and “inactive” state. A task scheduler is typically utilized to switch between the ready and active states. The kernel maintains a dynamic list or queue to organize the ready tasks so that they are executed in accordance with their priority. For purposes of description herein, a “task” is alternately referred to as a thread or process.
Interruption of an active task and setting up the state of another task (e.g. thread) for execution, is referred to as context switching. Context switching requires that the machine state registers (storing the execution state) of the interrupted task be saved to memory such that the task execution state may be restored when the task's active status is restored. Also, the kernel maintains the run queue in which tasks are queued. Other kernel components such as an I/O manager may request rescheduling responsive to a higher priority task having entered the ready state from an inactive state. The associated functions of continuous priority review and context switching substantially impacts throughput of priority tasks.
Managing memory resources is a key feature of any multitasking system. Modern operating systems employ memory managers that, in conjunction with hardware, support so-called virtual memory in which applications use “virtual addresses” to access memory. During program execution, the virtual addresses are converted into real memory addresses enabling the virtual memory to feature fault isolation among applications. Furthermore, virtual memory uses a paging technique in which larger and less expensive storage devices, such as hard disk space, is used to effectively extend the amount of available memory beyond what is provided by the systems “real memory,” typically random access memory (RAM).
A problem arises in many systems, such as embedded systems, in which memory resources may be constrained in a manner that has implications for task scheduling and execution. Embedded systems are special-purpose systems that provide a sub-function in a large, complex system such as a service processor in a large multiprocessor system, or which may be completely encapsulated by its host device. In addition to service processors, embedded systems are implemented in mobile telephones, personal data assistants, automatic teller machines, computer printers, and other special purpose devices.
In an embedded environment, both real memory, dynamic random access memory (DRAM), for example, and persistent storage in the form of programmable read-only memory (PROM), such as Flash memory, are limited due to space and budget constraints. Use of virtual memory paging techniques is particularly impractical when the alternate, persistent storage resources are circuit-based (Flash memory, for example) rather that magnetic or optical disk media, the cost per byte is greater than for the real memory itself.
As a result of the foregoing, applications running in embedded systems are limited by the amount of available physical memory. In such systems, if an application requests more memory than is presently available, a fatal error and termination of one or more program threads may result.
Under many operating systems, an “out of memory” condition is addressed by the kernel, which either selects a process/thread to terminate or fails an application requesting memory. For most computer systems, such as personal computers having substantial memory capacity and disk space that are further leveraged using virtual memory paging, an out of memory condition rarely occurs. In case the condition does arise, these systems usually select a non-vital process to terminate such that a system wide failure is avoided.
For specialized systems, such as embedded systems that perform system-critical functions and have limited memory resources, an out of memory condition may result in a system crash not readily recoverable from. It can therefore be appreciated that a need exists for a method and system for performing process multitasking in a manner addressing memory resource limitation constraints. The present invention addresses this and other needs unaddressed by the prior art.